import java.util.Deque;
import java.util.LinkedList;

class Solution {
    // bfs / union / dfs 都可以
    public int numIslands(char[][] grid) {
        int[][] forward = new int[][] {
                {1,0},{-1,0},{0,1},{0,-1}
        };
        int res = 0;
        int n = grid.length,m = grid[0].length;
        for(int i =0;i<n;i++) {
            for(int j =0;j<m;j++) {
                if(grid[i][j] == '1') {
                    res ++;
                    // 进行bfs
                    Deque<int[]> queue = new LinkedList<>();
                    grid[i][j] = '0';
                    queue.add(new int[]{i,j});
                    while(!queue.isEmpty()) {
                        int[] t = queue.pop();
                        int x = t[0],y = t[1];
                        for(int k =0;k<4;k++) {
                            int tx = x + forward[k][0];
                            int ty = y + forward[k][1];
                            if(tx < 0 || tx >= n || ty < 0 || ty >= m || grid[tx][ty] != '1') {
                                continue;
                            }
                            grid[tx][ty] = '0';
                            queue.add(new int[]{tx,ty});
                        }
                    }
                }
            }
        }
        return res;
    }


}